Many processors comprise a branch predictor which predicts which direction the program flow will take in the case of instructions known to cause possible flow changes, such as branch instructions. Branch prediction is useful as it enables instructions to be speculatively executed by the processor before the outcome of the branch instruction is known.
Branch instructions may be classified as conditional or indirect. Conditional branch instructions (branch instructions based on a constant value) require a binary decision as to whether the branch is taken or not-taken. Indirect branch instructions (branch instructions based on a variable) require an N-ary decision as to the target address where N is the number of possible target addresses. Accordingly indirect branches are more difficult to predict than conditional branches. As a result, many branch predictors are unable to accurately predict indirect branch instructions.
One solution to this has been to improve the indirect branch prediction algorithm used by the branch predictor. However, this is often quite difficult and time intensive.
The embodiments described below are not limited to implementations which solve any or all of the disadvantages of known processors.